package com.moyoutian.leetcode;

import com.moyoutian.utils.ArrayUtils;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 1996. 游戏中弱角色的数量
 * <p>
 * <p>
 * 你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击 和 防御 。给你一个二维整数数组 properties ，其中 properties[i] = [attacki, defensei] 表示游戏中第 i 个角色的属性。
 * <p>
 * <p>
 * 如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级，则认为该角色为 弱角色 。更正式地，如果认为角色 i 弱于 存在的另一个角色 j ，那么 attackj > attacki 且 defensej > defensei 。
 * <p>
 * <p>
 * 返回 弱角色 的数量。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：properties = [[5,5},{6,3},{3,6]]
 * <p>
 * 输出：0
 * <p>
 * 解释：不存在攻击和防御都严格高于其他角色的角色。
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：properties = [[2,2},{3,3]]
 * <p>
 * 输出：1
 * <p>
 * 解释：第一个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。
 * <p>
 * <p>
 * 示例 3：
 * <p>
 * <p>
 * 输入：properties = [[1,5},{10,4},{4,3]]
 * <p>
 * 输出：1
 * <p>
 * 解释：第三个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。
 * <p>
 * <p>
 * 提示：
 * <p>
 * <p>
 * 2 <= properties.length <= 105
 * <p>
 * properties[i].length == 2
 * <p>
 * 1 <= attacki, defensei <= 105
 * <p>
 * <p>
 * 通过次数8,186提交次数26,489
 */
public class Demo1996 {

    public static void main(String[] args) {
//        int[][] properties = {{5, 5}, {6, 3}, {3, 6}};
//        int[][] properties = {{1, 5}, {10, 4}, {4, 3}};
//        int[][] properties = {{1, 1}, {2, 1}, {2, 2}, {1, 2}};
//        int[][] properties = {{2, 2}, {3, 3}};
//        int[][] properties = {{10, 10}, {9, 1}, {8, 9}};
        int[][] properties = {{7, 9}, {10, 7}, {6, 9}, {10, 4}, {7, 5}, {7, 10}};

        System.out.println(numberOfWeakCharacters(properties));
        for (int i = 0; i < properties.length; i++) {
            ArrayUtils.printArray(properties[i]);
        }
    }

    public static int numberOfWeakCharacters(int[][] properties) {
        int re = 0;
        int maxAttack = 0;
        int maxDefense = 0;
        //最值
        for (int[] property : properties) {
            maxAttack = Math.max(maxAttack, property[0]);
            maxDefense = Math.max(maxDefense, property[1]);
        }

        int[] maxAttacks = new int[maxAttack + 2];
        //找到同一个键的最大值
        for (int[] property : properties) {
            maxAttacks[property[0]] = Math.max(maxAttacks[property[0]], property[1]);
        }
        //做出对应的表格
        int c = 0;
        for (int i = maxAttacks.length - 1; i >= 0; i--) {
            if (c > maxAttacks[i]) {
                maxAttacks[i] = c;
            } else {
                c = maxAttacks[i];
            }
        }
        //根据表格计算结果
        for (int[] property : properties) {
            if (property[1] < maxAttacks[property[0] + 1]) {
                re++;
            }
        }
        return re;
    }

    public static int numberOfWeakCharacters11(int[][] properties) {
        int re = 0;
        Arrays.sort(properties, (o1, o2) -> o1[0] == o2[0] ? (o1[1] - o2[1]) : (o2[0] - o1[0]));
        //寻找最大值
        int max = 0;
        for (int i = 0; i < properties.length; i++) {
            if (properties[i][1] < max) {
                re++;
            } else {
                max = properties[i][1];
            }
        }
        return re;
    }

    public static int numberOfWeakCharacters1(int[][] properties) {
        int re = 0;
        Arrays.sort(properties, (o1, o2) -> o1[0] == o2[0] ? (o1[1] - o2[1]) : (o2[0] - o1[0]));
        //寻找最大值
        int max = properties[0][0];
        int group = max;//当前组
        int groupMax = properties[0][1];//当前组最大值
        int lGroup = max;//上一组
        int lGroupMax = properties[0][1];//上一组最大值
        for (int i = 0; i < properties.length; i++) {
            if (group != properties[i][0]) {//下一组

                lGroup = Math.max(group, lGroup);//上一组
                lGroupMax = Math.max(groupMax, lGroupMax);//上一组最大值

                group = properties[i][0];//当前组
                groupMax = properties[i][1];//当前组最大值

            }
            if (max > properties[i][0] && lGroupMax > properties[i][1]) {
                re++;
            }
        }
        return re;
    }
}
